#!/usr/bin/env python
#-*- coding: utf-8 -*-
#__author__:vincentlc
#time: 16/4/3 : 13:48

'''
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

'''

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums != None:

            if len(nums) != 0:
                major_element = nums[0]
                max_count = 0
                dict_t = {}
                for i in nums:
                    if i in dict_t:
                        dict_t[i]+=1
                        if dict_t[i] > dict_t[major_element]:
                            major_element = i
                    else:
                        dict_t[i] = 1
                print (major_element)
                print (dict_t[major_element])
            else:
                return None
    def majorityElement2(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums != None:
            count = len(nums)/2
            if count != 0:
                major_element = nums[0]
                max_count = 0
                dict_t = {}
                for i in nums:
                    if i in dict_t:
                        dict_t[i]+=1
                        # if dict_t[i] > dict_t[major_element]:
                        if dict_t[i] > count:
                            major_element = i
                    else:
                        dict_t[i] = 1
                # return dict_t[major_element]
                return major_element
            else:
                return None
a = Solution()
# test1 = [1,2,3,4,1,2,1]
test1 = [1,2,3,4,2,1,2,1]
# test1 = []
# test1 = [1]
print (a.majorityElement2(test1))



